import java.util.Deque;
import java.util.LinkedList;

/**
 * 32. 最长有效括号
 */
public class Solution_32 {
    /**
     * 官方题解：栈
     * <p>
     * 始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」
     * <p>
     * 时间复杂度：O(N)
     * 空间复杂度：O(N)
     * 
     * @param s
     * @return
     */
    public int longestValidParentheses(String s) {
        int ans = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                // 对每个 '('，将其下标入栈
                stack.push(i);
            } else {
                // 对每个 ')'，先弹出栈顶元素表示匹配了当前右括号
                stack.pop();
                // 如果栈为空，说明当前的右括号为没有被匹配的右括号，
                // 将其下标放入栈中来更新之前的「最后一个没有被匹配的右括号的下标」
                // 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    ans = Math.max(ans, i - stack.peek());
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution_32 solution = new Solution_32();
        String s = ")()())";
        int ans = solution.longestValidParentheses(s);
        System.out.println(ans);
    }
}
